package offer;


/**
 * @Author SSK
 * @Date Created in 23:00 2019/8/8
 * @Description 矩阵中的路径
 * @Version 1.0
 */
public class T66 {
    final static int[][] WZ = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        boolean[] vis = new boolean[matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            vis[i] = false;
        }
        for (int i = 0; i < matrix.length; i++) {
                if (matrix[i]==str[0]) {
                    vis[i] = true;
                    if (dfs(matrix,rows,cols,str,i,1,vis)) {
                        return true;
                    }
                    vis[i] = false;
                }
        }
        return false;
    }
    public boolean dfs(char[] matrix, int rows, int cols, char[] str, int wz,int index, boolean[] vis) {

        if (index==str.length) {
            return true;
        }
        int x = wz/cols;
        int y = wz%cols;
        boolean flag = false;
        for (int i = 0; i < 4; i++) {
            int wx = x + WZ[i][0];
            int wy = y + WZ[i][1];
            int w = wx*cols+wy;
            if (wx>=0&&wx<rows&&wy>=0&&wy<cols&&!vis[w]&&matrix[w]==str[index]) {
                vis[w] = true;
                flag = flag || dfs(matrix,rows,cols,str,w,index+1,vis);
                vis[w] = false;
            }
        }

        return flag;
    }
    public static void main ( String[] args) {
        char[] chars = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS".toCharArray();
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 8; j++) {
                System.out.print(chars[i*8+j]+" ");
            }
            System.out.print("\n");
        }
        System.out.println(new T66().hasPath("ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS".toCharArray(),5,8,"SGGFIECVAASABCEHJIGQEMS".toCharArray()));

    }
}
